#ifndef KL_H
#define KL_H

#include <cstdlib>
#include "grafo.h"
#include <cstdio>
#include <cmath>

typedef struct _cell{
  
  int no;
  _cell * prox;
  _cell * ant;

}cell;


class KL {

  public:
    KL(Grafo *grf, int tot, double fB);
    
  private:

	cell *bucket[2];	// bucket para a particao A (0) e a B (1)
	int topo[2];		// ponteiro para o topo do bucket de cada particao
				// 		o topo é a primeira posição ocupada
	cell** pt; 		// vetor de ponteiros para os vertices
	int *particao;
	int *particao_otima;
	int *custo;		// vetor que guarda o custo por mudar cada vertice de particao

	double fatorBalanceamento;

	int gmax;		// ganho maximo ao mudar um vertice de posição
	int n;

	Grafo *grafo;
	int total;
	
	int pesoParticao[2];

	void preencheGanhoMax(void);
	void preencheBuckets(void);
	void insere(int no, int ganho, int p);
	void remove(int no);
	cell* melhor(int p);
	void remove_melhor(int p);
	void atribuiParticaoOtima(void);
	void preenchePesoParticao(void);
	void refina (void);
};


#endif